/* 
 * trans.c - Matrix transpose B = A^T
 *
 * Each transpose function must have a prototype of the form:
 * void trans(int M, int N, int A[N][M], int B[M][N]);
 *
 * A transpose function is evaluated by counting the number of misses
 * on a 1KB direct mapped cache with a block size of 32 bytes.
 */ 
#include <stdio.h>
#include "cachelab.h"

int is_transpose(int M, int N, int A[N][M], int B[M][N]);

/* 
 * transpose_submit - This is the solution transpose function that you
 *     will be graded on for Part B of the assignment. Do not change
 *     the description string "Transpose submission", as the driver
 *     searches for that string to identify the transpose function to
 *     be graded. 
 */
char transpose_submit_desc[] = "Transpose submission";
void transpose_submid32(int M, int N, int A[N][M], int B[M][N])
{
    const int len = 8;
    int a, b, c, d, e, f, g, h, k, s;
    for (int i = 0; i < N; i += len) {
        for (int j = 0; j < N; j += len) {
            // copy
            for (k = i, s = j; k < i + len; k++, s++) {
                a = A[k][j];
                b = A[k][j + 1];
                c = A[k][j + 2];
                d = A[k][j + 3];
                e = A[k][j + 4];
                f = A[k][j + 5];
                g = A[k][j + 6];
                h = A[k][j + 7];
                B[s][i] = a;
                B[s][i + 1] = b;
                B[s][i + 2] = c;
                B[s][i + 3] = d;
                B[s][i + 4] = e;
                B[s][i + 5] = f;
                B[s][i + 6] = g;
                B[s][i + 7] = h;
            }
            // transpose
            for (k = 0; k < len; k++) {
                for (s = k + 1; s < len; s++) {
                    a = B[k + j][s + i];
                    B[k + j][s + i] = B[s + j][k + i];
                    B[s + j][k + i] = a;
                }
            }
        }
    }
}

void transpose_submit64(int M, int N, int A[N][M], int B[M][N])
{
    int a, b, c, d, e, f, g, h, i, j, k, l;
    for (i = 0; i < N; i += 8)
    {
        for (j = 0; j < M; j += 8) {
            for (k = i; k < i + 4; k++) {
                a = A[k][j];
                b = A[k][j + 1];
                c = A[k][j + 2];
                d = A[k][j + 3];
                e = A[k][j + 4];
                f = A[k][j + 5];
                g = A[k][j + 6];
                h = A[k][j + 7];

                B[j][k] = a;
                B[j + 1][k] = b;
                B[j + 2][k] = c;
                B[j + 3][k] = d;
                B[j][k + 4] = e;
                B[j + 1][k + 4] = f;
                B[j + 2][k + 4] = g;
                B[j + 3][k + 4] = h;
            }
            for (l = j; l < j + 4; l++) {
                a = A[i + 4][l];
                b = A[i + 5][l];
                c = A[i + 6][l];
                d = A[i + 7][l];
                e = B[l][i + 4];
                f = B[l][i + 5];
                g = B[l][i + 6];
                h = B[l][i + 7];

                B[l][i + 4] = a;
                B[l][i + 5] = b;
                B[l][i + 6] = c;
                B[l][i + 7] = d;
                B[l + 4][i] = e;
                B[l + 4][i + 1] = f;
                B[l + 4][i + 2] = g;
                B[l + 4][i + 3] = h;
            }
            for (k = i + 4; k < i + 8; k++) {
                a = A[k][j + 4];
                b = A[k][j + 5];
                c = A[k][j + 6];
                d = A[k][j + 7];
                B[j + 4][k] = a;
                B[j + 5][k] = b;
                B[j + 6][k] = c;
                B[j + 7][k] = d;
            }
        }
    }
}

void transpose_submid61(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, h, k;
    for (i = 0; i < N; i += 17)
    {
        for (j = 0; j < M; j += 17)
        {
            for (h = i; h < i + 17 && h < N; h++)
            {
                for (k = j; k < M && k < j + 17; k++)
                {
                    B[k][h] = A[h][k];
                }
            }
        }
    }
}
/* 
 * You can define additional transpose functions below. We've defined
 * a simple one below to help you get started. 
 */ 

/* 
 * trans - A simple baseline transpose function, not optimized for the cache.
 */
char trans_desc[] = "Simple row-wise scan transpose";
void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            tmp = A[i][j];
            B[j][i] = tmp;
        }
    }    

}

/*
 * registerFunctions - This function registers your transpose
 *     functions with the driver.  At runtime, the driver will
 *     evaluate each of the registered functions and summarize their
 *     performance. This is a handy way to experiment with different
 *     transpose strategies.
 */
void registerFunctions()
{
    /* Register your solution function */
    registerTransFunction(transpose_submit, transpose_submit_desc); 

    /* Register any additional transpose functions */
    registerTransFunction(trans, trans_desc); 

}

/* 
 * is_transpose - This helper function checks if B is the transpose of
 *     A. You can check the correctness of your transpose by calling
 *     it before returning from the transpose function.
 */
int is_transpose(int M, int N, int A[N][M], int B[M][N])
{
    int i, j;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; ++j) {
            if (A[i][j] != B[j][i]) {
                return 0;
            }
        }
    }
    return 1;
}

